package backtrace;

import java.util.HashSet;
import java.util.Set;

// 思路：DFS，按行选，选择某一行后，将对应列、对应左对角线、对应右对角线标记为不可填。
// 左对角线满足 行 + 列 = 定值
// 右对角线满足 行 - 列 = 定值
public class leetcode52N皇后2 {
    int sum;
    public int totalNQueens(int n) {
        Set<Integer> column = new HashSet<>();
        Set<Integer> left = new HashSet<>();
        Set<Integer> right = new HashSet<>();
        dfs(n, 0, column, left, right);
        return sum;
    }

    public void dfs(int n, int level, Set<Integer> column, Set<Integer> left, Set<Integer> right) {
        if (level == n) {
            sum++;
            return;
        } else {
            for (int i = 0; i < n; i++) {
                if (column.contains(i)) {
                    continue;
                }
                int leftRel = level + i;
                if (left.contains(leftRel)) {
                    continue;
                }
                int rightRel = level - i;
                if (right.contains(rightRel)) {
                    continue;
                }
                column.add(i);
                left.add(leftRel);
                right.add(rightRel);
                dfs(n, level + 1, column, left, right);
                column.remove(i);
                left.remove(leftRel);
                right.remove(rightRel);
            }
        }
    }
}
